from typing import Optional
from tree_node import TreeNode,build_tree_node


class Solution:
    """
    平衡二叉树：
    原始定义：该树的所有节点的左右子树高度相差不超过1

    """

    def isBalanced(self, root: Optional[TreeNode]) -> bool:

        def depth(node)->int:
            if not node:
                return 0
            
            left_depth=depth(node.left)
            if left_depth==-1:
                return -1
            right_depth=depth(node.right)
            if right_depth==-1:
                return -1

            if abs(left_depth-right_depth)>1:
                return -1

            return max(left_depth,right_depth)+1
        
        return depth(root)!=-1

        pass

if __name__=='__main__':

    arr=[1,None,2,None,3]
    root=build_tree_node(arr)

    s=Solution()
    res=s.isBalanced(root)
    print(res)